package com.xiaoyu.dp;

import java.util.Arrays;

/**
 * @program: DS_and_A
 * @description: 不同路径
 *
 * 一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
 *
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 *
 * 问总共有多少条不同的路径？
 *
 * 例:
 * 输入：m = 3, n = 7
 * 输出：28
 *
 * 如果向下走一步，那么会从 (i-1, j) 走过来；如果向右走一步，那么会从 (i, j-1) 走过来。
 * 因此我们可以写出动态规划转移方程：
 *  f(i,j)=f(i−1,j)+f(i,j−1) --->
 *
 * @author: YuWenYi
 * @create: 2021-05-24 10:09
 **/

/*
*   错误思路: 还是没有掌握DP的精髓,没有悟透这个DP的转移方程
*   public void helper(int m ,int n ,int row,int col,boolean[][] map){
        if (map[map.length-1][map[0].length-1]){
            ++count;
            return;
        }
        //如果row为2,说明走到了最下面,那么此时只能往右边走
        if (col < n-1 && row == m){
            map[row][col+1] = true;
            helper(m, n, row, col + 1, map);
        }else if (row < m-1 && col == n){//col同理
            map[row+1][col] = true;
            helper(m, n, row + 1, col, map);
        }else if (col < n-1 && row < m-1){
            map[row][col+1] = true;
            helper(m, n, row, col + 1, map);

            map[row+1][col] = true;
            helper(m, n, row + 1, col, map);
        }
    }
*
* */
public class UniquePaths_62 {

    //f(i,j)=f(i−1,j)+f(i,j−1) ---> 走到i,j位置的所有可能路径和,等于其其回退一步的可能路径之和!
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];  //代表m行n列的网格中每一格有多少条不同的路径!
        //对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界上，所以路径的可能性值只能是1!!!
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
               dp[i][j] = dp[i-1][j] + dp[i][j-1];  //使用动态转移方程
            }
        }
        return dp[m-1][n-1];
    }


    //进行空间优化!
    /*  //空间优化1:让pre去记录上一行的所有路径可能值
    *   int[] pre = new int[n];
        int[] cur = new int[n];
        Arrays.fill(pre, 1);
        Arrays.fill(cur,1);
        for (int i = 1; i < m;i++){
            for (int j = 1; j < n; j++){
                cur[j] = cur[j-1] + pre[j];
            }
            pre = cur.clone();
        }
        return pre[n-1];
    *
    * //空间优化二:重复利用dp数组,把pre给省略了
    *
    * 一维的dp数组定义为当前行中，每个元素对应的步数。
    *  二维dp数组dp[i][j] = dp[i-1][j] + dp[i][j-1]很好理解
    *  转化为一维数组， 对于第i行来说，dp[j] = dp[j] + dp[j-1],
    *  等号右边的未赋值之前的dp[j]就是上一行的第j个数据对应的步数，即dp[i-1][j]
    *  等号右边的dp[j-1]是已经更新过的本行的第j-1个数据对应的步数，即dp[i][j-1]
    *  则，本行的dp[j] = 上一行的dp[j] + 本行的dp[j-1]， 所以dp[j] = dp[j] + dp[j-1]，
    *  即dp[j] += dp[j-1].
    *
    *  假设m=3 n=4
    *  那么cur[n] 初始化后-->cur为:[1,1,1,1] -->即为第一行中所有格子的可能路径!
    *  开始循环:
    *     从第二行开始,dp[j]现在是等于上一行的该列的值,dp[j-1]是在上一个循环已经更新过的当前值的前一个值
    *     因此两个值相加后,修改dp[j]的值为当前行现在的值,其实最终还是f(i,j)=f(i−1,j)+f(i,j−1)
    *     循环结束后,第二行为:[1,2,3,4]
    *
    *     同理,第三行为:[1,3,6,10],即最后的答案为10,即dp[n-1]的值!
    * */
    public int uniquePaths1(int m, int n) {
        int[] cur = new int[n];  //记录一行的所有可能值,并且重复利用它
        Arrays.fill(cur, 1);

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                cur[j] = cur[j] + cur[j-1];
            }
        }
        return cur[n-1];
    }



    public static void main(String[] args) {
        UniquePaths_62 uniquePaths62 = new UniquePaths_62();
        System.out.println(uniquePaths62.uniquePaths1(3, 3));
    }
}
